package 动态规划;

public class 爬楼梯_无后效性 {
    /**
     *  带约束的爬楼梯
     *  给定一个共有n阶的楼梯，你每步可以上1阶或者2阶，但不能连续两轮跳1阶，请问有多少种方案可以爬到楼顶？
     *
     *  要求是不能连续跳1阶，没说不能连续跳2阶，每次往下一步跳的时候还要考虑上一次是怎么跳的
     *  设 dp[i][j] 表示当前在 i 台阶上，且是通过跳 j 阶到 i 的，因此有如下推算
     *
     *  dp[i][1] 表示上一次跳1阶到i
     *  dp[i][2] 表示上一次跳2阶到i
     *
     *  要想抵达 dp[i] 要么通过 dp[i-1] 达到，要么通过 dp[i-2] 到达
     *
     *  dp[i-1] 表示当前i台阶的前一个台阶，如果通过这一步抵达 dp[i] 则只需要跳一步即可，那么只能一次性跳2阶抵达 dp[i-1] 才行，不然就无法满足【不能连续跳2轮1阶】
     *  dp[i-2] 表示当前i台阶的前两个台阶，既然是通过跳2个台阶到i的，那么在 i-2 之前可以调1阶到 i-2 也可以跳2阶到 i-2
     *
     *  因此可以得到
     *
     *  dp[i][1] = dp[i-1][2]
     *  dp[i][2] = dp[i-2][1] + dp[i-2][2]
     *
     */

    /* 带约束爬楼梯：动态规划 */
    static int climbingStairsConstraintDP(int n) {
        if (n == 0) {
            return 0;
        }
        if (n <= 2) {
            return 1;
        }
        int[][] dp = new int[n+1][3];
        dp[0][1] = 0;
        dp[0][2] = 0;
        dp[1][1] = 1;
        dp[1][2] = 0;
        dp[2][1] = 0;
        dp[2][2] = 1;
        for (int i =3; i <= n; i++) {
            dp[i][1] = dp[i-1][2];
            dp[i][2] = dp[i-2][1] + dp[i-2][2];
        }
        return dp[n][1] + dp[n][2];
    }

    public static void main(String[] args) {
        System.out.println(climbingStairsConstraintDP(3));
    }
}
